package basis.netease.medium;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 7-21 连续数列
 * 给定一个整数数组，找出总和最大的连续数列，并返回总和。
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 * 输入格式:
 * 数组nums
 * 输出格式:
 * 连续子数组的最大和
 * 输入样例:
 * 在这里给出一组输入。例如：
 * -2,1,-3,4,-1,2,1,-5,4
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 6
 * 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
 */
public class Main_18 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = Arrays.stream(scanner.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        System.out.println(maxSubArraySum(arr));

    }

    public static int maxSubArraySum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int maxSum = arr[0];
        int tmp = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (tmp <= 0) {
                tmp = arr[i];
            } else {
                tmp += arr[i];
            }
            maxSum = Math.max(tmp, maxSum);
        }
        return maxSum;
    }

}
